|
In combinatorial mathematics, group testing refers to any procedure which breaks up the task of locating elements of a set which have certain properties into tests on subsets ("groups") rather than on individual elements. A familiar example of this type of technique is the false coin problem of recreational mathematics. In this problem there are ''n'' coins and one of them is false, weighing less than a real coin. The objective is to find the false coin, using a balance scale, in the fewest number of weighings. By repeatedly dividing the coins in half and comparing the two halves, the false coin can be found quickly as it is always in the lighter half.〔A bit more precisely – if there are an odd number of coins to be weighed, pick one to put aside and divide the rest into two equal piles. If the two piles have equal weight, the bad coin is the one put aside, otherwise the one put aside was good and no longer has to be tested.〕 Schemes for carrying out such group testing can be simple or complex and the tests involved at each stage may be different. Schemes in which the tests for the next stage depend on the results of the previous stages are called ''adaptive procedures'', while schemes designed so that all the tests are known beforehand are called ''non-adaptive procedures''. The structure of the scheme of the tests involved in a non-adaptive procedure is known as a pooling design. ==Background== Robert Dorfman's paper in 1943 introduced the field of (Combinatorial) Group Testing. The motivation arose during the Second World War when the United States Public Health Service and the Selective service embarked upon a large scale project. The objective was to weed out all syphilitic men called up for induction. However, syphilis testing back then was expensive and testing every soldier individually would have been very cost heavy and inefficient. A basic breakdown of a test is: * Draw sample from a given individual * Perform required tests * Determine presence or absence of syphilis Say we have soldiers, then this method of testing leads to tests. If we have 70-75% of the people infected then the method of individual testing would be reasonable. Our goal however, is to achieve effective testing in the more likely scenario where it does not make sense to test 100,000 people to get (say) 10 positives. The feasibility of a more effective testing scheme hinges on the following property. We can combine blood samples and test a combined sample together to check if at least one soldier has syphilis. Modern interest in these testing schemes has been rekindled by the Human Genome Project. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Group testing」の詳細全文を読む スポンサード リンク
|